package algorithms.leaning.class23;

import common.util.MyUtil;

/**
 * N皇后问题是指在N*N的棋盘上要摆N个皇后，
 * 要求任何两个皇后不同行、不同列， 也不在同一条斜线上
 * 给定一个整数n，返回n皇后的摆法有多少种。
 * n=1，返回1
 * n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0
 * n=8，返回92
 *
 * @author guichang
 * @date 2021/6/26
 */

@SuppressWarnings("all")
public class Code3_动态规划_N皇后 {

    public static void main(String[] args) {
        for (int i = 1; i <= 12; i++) {
            MyUtil.printf("{}皇后摆法：{}", i, nQueen(i));
        }
    }

    public static int nQueen(int n) {
        if (n <= 0) {
            return 0;
        }
        return process(0, new int[n]);
    }

    /**
     * 当前来到第i行，i-1及以上的决定放在record数组中，返回能放下的方法数
     * record[x]=y表示第x行的皇后放在了y列上
     */
    private static int process(int i, int[] record) {
        // 总列数
        int N = record.length;
        // 能来到最后表示前面的都有效
        if (i == N) {
            return 1;
        }
        // 枚举皇后在每列的情况
        int ways = 0;
        for (int j = 0; j < N; j++) {
            if (valid(record, i, j)) {
                record[i] = j;
                ways += process(i + 1, record);
            }
        }
        return ways;
    }

    /**
     * 判断 [i,j]位置的皇后是否合理
     */
    private static boolean valid(int[] record, int i, int j) {
        for (int k = 0; k < i; k++) {
            // 共列
            if (j == record[k]) {
                return false;
            }
            // 共斜线
            if (Math.abs(i - k) == Math.abs(j - record[k])) {
                return false;
            }
        }
        return true;
    }

}